package com.problem.leetcode;

import com.google.common.base.Stopwatch;

import java.util.ArrayList;
import java.util.List;

/**
 * 解法1:时间复杂度与空间复杂度都很高，主要采用hashmap存储数据
 * 解法2: 由于都是小写字符，所以统计每个字符串小写字符出现的次数
 *
 * @author didi
 * @DESCRIPTION
 * @create 2019-04-05 11:37
 **/

public class Problem1002 {

    // public List<String> commonChars(String[] A) {
    //     List<String>               list     = new ArrayList<>();
    //     HashMap<String, Integer>[] hashMaps = new HashMap[A.length];
    //
    //     for (int index = 0; index < A.length; index++) {
    //         HashMap<String, Integer> hashMap = new HashMap<>();
    //         for (int cIndex = 0; cIndex < A[index].length(); cIndex++) {
    //             String tmp = String.valueOf(A[index].charAt(cIndex));
    //             if (hashMap.containsKey(tmp)) {
    //                 hashMap.put(tmp, hashMap.get(tmp) + 1);
    //             } else {
    //                 hashMap.put(tmp, 1);
    //             }
    //         }
    //         hashMaps[index] = hashMap;
    //     }
    //
    //     int shortIndex = 500;
    //     for (int index = 0; index < A.length; ++index) {
    //         if (A[index].length() < shortIndex) {
    //             shortIndex = index;
    //         }
    //     }
    //     //找到字符串长度最小的字符串
    //     //遍历最短字符串
    //     for (Map.Entry<String, Integer> entry : hashMaps[shortIndex].entrySet()) {
    //         boolean isFind = true;
    //         int     value  = 10000;
    //         for (int index = 0; index < hashMaps.length; index++) {
    //             if (index != shortIndex) {
    //                 if (!hashMaps[index].containsKey(entry.getKey())) {
    //                     isFind = false;
    //                     break;
    //                 }
    //                 value = Math.min(value, hashMaps[index].get(entry.getKey()));
    //             }
    //         }
    //         //都有该字符串 添加到list中
    //         if (isFind) {
    //             for (int sIndex = 0; sIndex < Math.min(entry.getValue(), value); sIndex++) {
    //                 list.add(entry.getKey());
    //             }
    //         }
    //
    //     }
    //
    //     return list;
    // }

    public List<String> commonChars(String[] A) {
        List<String> list = new ArrayList<>();

        int[] base = map(A[0]);
        for (int index = 1; index < A.length; index++) {
            int[] compare = map(A[index]);
            reduce(base, compare);
        }

        for (int index = 0; index < base.length; index++) {
            for (int j = 0; j < base[index]; j++) {
                list.add(String.valueOf((char) (index + 'a')));
            }
        }

        return list;
    }

    private void reduce(int[] base, int[] compare) {
        for (int cIndex = 0; cIndex < base.length; cIndex++) {
            base[cIndex] = Math.min(base[cIndex], compare[cIndex]);
        }
    }

    private int[] map(String string) {
        int[] chars = new int[26];

        for (int index = 0; index < string.length(); index++) {
            chars[string.charAt(index) - 'a']++;
        }
        return chars;
    }


    public static void main(String[] args) {
        Problem1002 problem1002 = new Problem1002();
        Stopwatch   stopwatch   = Stopwatch.createStarted();
        for (int index = 0; index < 10000000; index++) {
            problem1002.commonChars(new String[]{"bella", "label", "roller"});
        }
        stopwatch.stop();
        System.out.println(stopwatch);


    }

}
